1. Field of the Invention
This invention relates to method and apparatus for generating the carry bits for the sum of two multi-bit inputs. More particularly this invention relates to a digital integrated circuit which generates the carry output within a minimum number of gate delays.
2. Art Background
Digital integrated circuitry, such as ripple carry adders and select carry adders, that performs the binary addition of two input values are well known and widely used. Each bit of the result is calculated from the sum of the corresponding two input bits and the carry-in, which is the carry generated from the sum of adjacent less significant bits and its carry-in. However, as the speed of the computers increase so does the need to increase the speed of all the digital circuitry utilized in or with the computer. This need is particularly evident in systems which employ 32 and 64 bit words. Ripple carry adders require upwards of 64 gate delays for a 32 bit adder because the processing of the more significant bits is dependent on the results of the processing of the lesser significant bits. For example, the sum of bit N is dependent upon whether there was a carry generated by the sum calculated for bit N-1. Similarly, the sum of bits N-1 is dependent upon the carry generated from the sum of bits N-2. Thus, the calculation of the more significant bits must be delayed until the carrys of the less significant bits are calculated. There are circuits that improve upon the number of gate delays. For example, in U.S. Pat. No. 4,682,303, a carry select adder is described in which, for example in a 32 bit case, the low 16 bits are summed and two sets of the upper 16 bits are calculated, the first group having a carry in signal of zero and the second group having a carry in signal of one wherein the output generated during the carry out generated due to the calculation of the lower 16 bits determines which result to choose. The '303 patent further optimizes this concept by breaking down the size of the 16 bit groups further into three sets of 8 adders. The patent describes circuitry in which the gate delays are decreased to 18 stages for a 32 bit computation. However, this method requires extensive and complex circuitry and 18 gate delays is a still an undesirable number of delays. U.S. Pat. No. 4,764,886, discloses a bit slice adder. The adder disclosed is similar to a ripple carry adder but two calculations are performed in parallel for each of the individual bits--the case where the carry-in has a value of zero and the case where the carry-in has a value of one. The output is multiplexed with the actual carry in bit selecting the output value. Although this method further decreases the time required for a 32 bit calculation, the adder still requires at least a significant number of gate delays to perform the calculation.